#include<iostream>
#include<vector>
using namespace std;
/*
给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。​
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
解题思路：
此题与买卖股票2不同，加了一个冷冻期，在卖出股票后的一天不能进行股票买入的操作，所以我们要将不持有股票的状态进行分隔
同理我们创建dp[i][0]表示持有股票的状态手中现金最大值
我们将不持有股票的状态细分为卖出股票的当天，冷冻期，冷冻期之后保持不持有股票的状态的手中现金的最大值
dp[i][1]表示卖出股票的当天
dp[i][2]表示冷冻期
dp[i][3]表示保持不持有股票的状态
下面逐一进行递推公式的推导
持有股票的状态可以由前一天就持有股票，前一天是冷冻期的状态买入股票，前一天是保持不持有股票的状态买入股票推导而来
dp[i][0] = max(dp[i-1][0],max(dp[i-1][2]-prices[i],dp[i-1][3]-prices[i]))
冷冻期的状态只能由前一天是卖出股票的状态推导而来
dp[i][2] = dp[i-1][1]
卖出股票的状态只能前一天是持有股票的状态推导而来
dp[i][1] = dp[i-1][0]+prices[i]
保持不持有股票的状态由冷冻期和前一天就已经是卖出股票的状态推导而来
dp[i][3] = max(dp[i-1][2],dp[i-1][3])
*/
int dp(vector<int> prices)
{
    //创建dp数组并初始化
    vector<vector<int>> dp(prices.size(),vector<int>(4,0));
    //第0天持有股票的状态
    dp[0][0] = -prices[0];
    dp[0][1] = 0;//第0天卖出股票的状态
    dp[0][2] = 0;//冷冻期
    dp[0][3] = 0;//根据递推公式设置初始值
    for(int i=1;i<prices.size();i++)
    {
        dp[i][0] = max(dp[i-1][0],max(dp[i-1][2]-prices[i],dp[i-1][3]-prices[i]));
        dp[i][1] = dp[i-1][0]+prices[i];
        dp[i][2] = dp[i-1][1];
        dp[i][3] = max(dp[i-1][2],dp[i-1][3]);
    }
    return max(dp[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));
}
int main()
{
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter nums:"<<endl;
    vector<int> nums(number);
    for(int i=0;i<number;i++)
        cin>>nums[i];
    cout<<dp(nums);
    return 0;
}